﻿#define _CRT_SECURE_NO_WARNINGS 1
//⼀个⻓度为n - 1的递增排序数组中的所有数字都是唯⼀的，并且每个数字都在范围0〜n - 1之内。
//在范围0〜n - 1内的n个数字中有且只有⼀个数字不在该数组中，请找出这个数字

//eg：输⼊:[0,1,2,3,4,5,6,7,9]  输出:8
#include <iostream>
using namespace std;

//二分查找算法解决即可
int missingNumber(int* nums,int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mid = left + (right - left) / 2;
		if (nums[mid] == mid) left = mid + 1;
		else right = mid;
	}
	return left == nums[left] ? left + 1 : left;
}

int main()
{
	int nums[] = { 0,1,2,3,4,5,6,7,9 };
	int n = sizeof(nums) / sizeof(nums[0]);

	int an=missingNumber(nums, n);
	cout << an << endl;

	return 0;
}